package com.itcam.recursion;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author : Cammy.Wu
 * Description : 
 */

public class RecursionTest01 {

    public static void main(String[] args) {
        // 1.求n的阶乘
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println("n! = " + f(n));

        // 2.反向输出字符串
        String str = "cammy nav";
        reversePrint(str, 0);
        System.out.println();

        int[] a = {3, 2, 6, 1, 5, 4, 7};
        bubble(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

        int[] a1 = {3, 2, 6, 1, 5, 7, 4};
        insertion(a1, 1, a1.length - 1);
        System.out.println(Arrays.toString(a1));

    }

    /**
     * 求阶乘
     * @param n
     * @return
     */
    private static int f(int n) {
        if (n == 1) {
            return 1;
        }
        return n * f(n - 1);
    }

    /**
     * 反转字符串并打印输出
     * @param str
     * @param index
     */
    public static void reversePrint(String str, int index) {
        if (index == str.length()) {
            return;
        }
        reversePrint(str, index + 1);
        System.out.print(str.charAt(index));
    }

    /**
     * 二分查找
     * @param a
     * @param target
     * @return
     */
    public static int binarySearch(int[] a, int target) {
        // 单路递归
        return recursion(a, target, 0, a.length - 1);
    }

    /**
     * 二分查找——单路递归
     * @param a
     * @param target
     * @param i
     * @param j
     * @return
     */
    private static int recursion(int[] a, int target, int i, int j) {
        if (i > j) {
            return -1;
        }
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            return recursion(a, target, i, m - 1);
        } else if (target > a[m]) {
            return recursion(a, target, m + 1, j);
        } else {
            return m;
        }
    }

    /**
     * 冒泡排序算法的实现
     *
     * @param a 待排序的数组
     * @param low 排序的起始索引
     * @param high 排序的结束索引
     */
    public static void bubble(int[] a, int low, int high) {
        // 如果起始索引等于结束索引，说明数组已经有序，直接返回
        if (low == high) {
            return;
        }
        // 初始化一个变量j，用于记录最后一次交换的位置
        int j = low;
        // 从起始索引开始，遍历到结束索引的前一个位置
        for (int i = low; i < high; i++) {
            // 如果当前元素大于下一个元素，则交换它们的位置
            if (a[i] > a[i + 1]) {
                swap(a, i, i + 1);
                // 更新j的值为当前交换的位置
                j = i;
            }
        }
        // 递归调用bubble方法，对数组的前j个元素进行排序
        bubble(a, low, j);
    }

    /**
     * 交换数组中两个元素的位置
     *
     * @param a 数组
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private static void swap(int[] a, int i, int j) {
        // 临时变量t，用于存储a[i]的值
        int t = a[i];
        // 将a[j]的值赋给a[i]
        a[i] = a[j];
        // 将t的值赋给a[j]，完成交换
        a[j] = t;
    }

    /**
     * 插入排序算法的实现
     *
     * @param a 待排序的数组
     * @param low 排序的起始索引
     * @param high 排序的结束索引
     */
    public static void insertion(int[] a, int low, int high) {
        // 如果起始索引大于结束索引，说明数组已经有序，直接返回
        if (low > high) {
            return;
        }
        // 初始化一个变量i，用于记录当前要插入的元素的索引
        int i = low - 1;
        // 记录当前要插入的元素的值
        int t = a[low];
        // 从当前要插入的元素的前一个位置开始，向前遍历
        while (i >= 0 && a[i] > t) {
            // 将当前元素向后移动一位
            a[i + 1] = a[i];
            // 更新i的值，继续向前遍历
            i--;
        }
        // 如果i + 1不等于low，说明当前元素需要插入到i + 1的位置
        if (i + 1 != low) {
            a[i + 1] = t;
        }
        // 递归调用insertion方法，对数组的下一个元素进行排序
        insertion(a, low + 1, high);
    }


}
